#include <stdio.h>
struct node {
	int data;
	struct node *next;
};

// https://www.cnblogs.com/yorkyang/p/10876604.html

// 1.给一个单链表，判断其中是否有环的存在；
// slow每次向前走一步，fast向前追了两步，因此每一步操作后fast到slow的距离缩短了1步，这样继续下去就会使得
// 两者之间的距离逐渐缩小; 
int exist_loop(struct node *head)
{
	struct node *slow, *fast;
	slow = fast = head;
	while (slow->next != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow) return 1;
	}
	return 0;
}

struct node *find_loop_meet(struct node *head)
{
	struct node *slow, *fast;
	slow = fast = head;
	while (slow->next != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow) return slow;
	}
	printf("Not loop!\n");
	return NULL;
}


// 2.如果存在环，找出环的入口点；
// 相遇时slow走过s，fast走过2s，入口到head距离a，入口到相遇点距离x；
// fast比slow多走n圈，环的长度为r; 链表长度L
// 故2s = s + nr (n>=1) → s = nr = (n-1)r + r = (n-1)r + L-a
// 又s = x+a; 所以a = (n-1)r + (L-x-a)，即入口到head的距离 = 相遇点到入口的距离
struct node *find_loop_start(struct node *head)
{
	struct node *ptr1 = head; //链表头
	struct node *ptr2 = find_loop_meet(head); //相遇点
	if (ptr2 == NULL) return NULL;	//没有环

	while (ptr1 != ptr2) {
		ptr1 = ptr1->next;
		ptr2 = ptr2->next;
	}
	return ptr1;
}

// 计算环内节点个数
int get_loop_length(struct node *head)
{
	int cnt = 1;
	struct node *start = find_loop_start(head);
	struct node *temp = start->next;
	while (temp != start) {
		cnt++;
		temp = temp->next;
	}
	return cnt;
}